/**
 * 494. 目标和
 * https://leetcode-cn.com/problems/target-sum/
 */

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function findTargetSumWays(nums, target) {
  let sum = 0;
  for (let i = 0; i < nums.length; i += 1) {
    sum += nums[i];
  }
  const capacity = (sum - target) / 2;
  if (capacity < 0 || !Number.isInteger(capacity)) {
    return 0;
  }
  const dp = new Array(nums.length + 1);
  for (let i = 0; i <= nums.length; i += 1) {
    dp[i] = new Array(capacity + 1).fill(0);
  }
  dp[0][0] = 1;
  for (let i = 1; i <= nums.length; i += 1) {
    const num = nums[i - 1];
    if (num > 0) {
      [dp[i][0]] = dp[i - 1];
    } else {
      dp[i][0] = dp[i - 1][0] * 2;
    }
  }
  for (let i = 1; i <= nums.length; i += 1) {
    const num = nums[i - 1];
    for (let j = 1; j <= capacity; j += 1) {
      if (num <= j) {
        dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num];
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[nums.length][capacity];
}

console.log(findTargetSumWays([1, 1, 1, 1, 1], 3) === 5);
console.log(findTargetSumWays([1], 1) === 1);
